Machine Learning Foundations - L2 Notes(上)

1. 前提
2. 一 Perceptron Hypothesis Set
1. 2.1. Perceptron
2. 2.2. 二維中的樣子
3. 二 Perceptron Learning Algorithm (PLA)

前提

章節名稱: learning to answer yes/no

延用上次提到的一些符號:

f : Target function
x : Input
y : Output
D : Data
h : hypothesis
g : 近似 f ，final hypothesis

接著要來講講如何讓電腦學習是非題。

一 Perceptron Hypothesis Set

Perceptron

繼續上次的例子，「是否核發信用卡給顧客」，給出一個判斷的演算法。

2-1-1

每個顧客會有其不同的特徵，像是薪資、負債等等，也就是這邊的 $x_1,x_2,\ldots$ ，就像是一個向量。
接著是每個特徵我們會給它權重(weight)，比較正相關的或是負相關，也就是這邊的 $w_1,w_2,\ldots$ ，也是一個向量。

將它們作內積後，可得到這位顧客的分數，再減去門檻值(threshold)後，就可得到 output ，good(+1) or bad(-1) or ignored(0)。

而這一個可能的公式，跟它最有關的則是其 weight 和 threshold ，我們可以改變它來得到不同的 Hypothesis。而這樣子的一個 Hypothesis 我們把它稱為 Perceptron(感知器) 。

經過數學的簡化，讓門檻值成為向量中的一份子，我們可把它寫成:

2-1-2

二維中的樣子

2-1-3

假設我們的特徵為二維的向量(加上門檻值的話就是一個假三維)，可以觀察出 $h(x)$ 它是條線。線的一邊是正的，另一邊是負的，核發或不核發。
而 $(x_1,x_2)$ 就是平面上的點了，自然也就代表某位顧客是否符合發信用卡的資格，圈圈或叉叉。

對應到剛講的 Perceptron ，可以了解到就是一個 線性的分類器 linear (binary) classifiers 。

二 Perceptron Learning Algorithm (PLA)

找出一條 Perceptron

那麼如何選出最好的 Hypothesis 也就是最好的那條線呢？再次強調我們所想要的是 f，但我們不知道它。
此時我們找了個 g 希望它近似 f，要怎知它有沒有近似 f 呢？
依現有的 Data (D) 來看，D 是 f 產生的。所以只要我們將 input 代進 g ，產生出的 y 可以與 Data 裡的相符，我們就可以說至少在現有的資料內，g 是和 f 相似的(甚至一樣)。

$g(x_n) = f(x_n) = y_n$

簡單來說，在資料裡是圈的，g 就要能把它分在圈，反之則是叉。

困難點在於，可能的 Perceptron 有 無限個 ，以二維來說就是有無限多條線。
所以找了一個方法，我們從某條線出發，依據 D 持續修正錯誤。

Perceptron Learning Algorithm

接下來因為每一個 hypothesis 都對應到一 w 向量，所以就用 $w_0$ 一組向量，來表示 $g_0$ 這條線。
那我們的目標則是讓線越來越好。

首先從某條線開始，$w_0$，它並不完美，意思就是在 某點會出錯 。
我們假設那點是 $(x_{n(t)},y_{n(t)})$ 。修正是一輪一輪的，t 表示現在在哪一輪。

我們將 w 和 x 做內積，得到的結果(sign)不等於 y => 出錯惹~~

我們要修正 w ，利用 $w_{t+1} = w_t + y_{n(t)}x_{n(t)}$

正確結果為 + :
y = +1 ，要使得 w 和 x 間的夾角變小。
正確結果為 - :
y = -1 ，要使得 w 和 x 間的夾角變大。

以內積來說，兩向量 夾角變小，其 值會變大； 夾角變大 ，其 值會變小 。( $\overrightarrow{A} \cdot \overrightarrow{B} = \vert{A}\vert\vert{B}\vert cos\theta$ ) 關於長度的問題，後面會提到。

而這邊 $w_t$ 為一向量，$x_{n(t)}$ 也為一向量， $y_{n(t)}$ 為一純量(+1 or -1)。
$w_t + y_{n(t)}x_{n(t)}$ 做向量加法，應該就是使下個 $w$ ，看是要更接近 $x$ 讓結果變為正， $y$ 為 +1；或遠離 $x$，使結果變為負， $y$ 為 -1。
(這邊沒很理解，不知道這樣解釋合不合理….

就這樣持續修正直到沒有錯誤，而最後產生的 w 則為 $w_{PLA}$。
PLA : Perceptron Learning Algorithm

2-2-1